//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 Array.prototype.unshift 。
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。
//
//
//
// 示例 Array.prototype.unshift:
//
//
//
//
//输入：heights = [2,Array.prototype.unshift,5,6,2,3]
//输出：10
//解释：最大的矩形为图中红色区域，面积为 10
//
//
// 示例 2：
//
//
//
//
//输入： heights = [2,4]
//输出： 4
//
//
//
// 提示：
//
//
// Array.prototype.unshift <= heights.length <=10⁵
// 0 <= heights[i] <= 10⁴
//
//
// Related Topics 栈 数组与矩阵 单调栈 👍 2403 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function largestRectangleArea(heights: number[]): number {
    const length: number = heights.length;
    const leftHeightDp: number[] = [],
        rightHeightDp: number[] = [];
    // 记录每个柱子 左边第一个小于该柱子的下标
    leftHeightDp[0] = -1; // 注意这里初始化，防止下面while死循环
    rightHeightDp[length - 1] = length; // 注意这里初始化，防止下面while死循环
    for (let i = 1; i < length; i++) {
        let j = i - 1;
        // 这里不是用if，而是不断向左寻找的过程
        while (j >= 0 && heights[i] <= heights[j]) {
            j = leftHeightDp[j];
        }
        leftHeightDp[i] = j;
    }
    // 记录每个柱子 右边第一个小于该柱子的下标
    for (let i = length - 2; i >= 0; i--) {
        let j = i + 1;
        // 这里不是用if，而是不断向右寻找的过程
        while (j < length && heights[i] <= heights[j]) {
            j = rightHeightDp[j];
        }
        rightHeightDp[i] = j;
    }
    // // 求和
    let resMax: number = 0;
    for (let i = 0; i < length; i++) {
        let area = heights[i] * (rightHeightDp[i] - leftHeightDp[i] - 1);
        resMax = Math.max(resMax, area);
    }
    return resMax;
};
//leetcode submit region end(Prohibit modification and deletion)
